package com.learning;

import Entry.Employee;
import Entry.ListNode;
import Entry.Node;
import Entry.TreeNode;

import java.util.*;

public class Easy {
    public String addStrings(String num1, String num2) {
        int len1=num1.length();
        int len2=num2.length();
        int i=len1-1;
        int j=len2-1;
        int c=0;
        int a;int b;
        String result="";
        while (i>=0&&j>=0){
            a=num1.charAt(i)-48;
            b=num2.charAt(j)-48;
            if(a+b+c>=10){
                result=(a+b+c-10)+result;
                c=1;
            }else {
                result=a+b+c+result;
                c=0;
            }
            i--;j--;
        }
        if(i>0&&j>0){
        }else if(i>=0){
            while (i>=0){
                a=num1.charAt(i)-48;
                if(a+c>=10){
                    result=(a+c-10)+result;
                    c=1;
                }else {
                    result = a+c + result;
                    c=0;
                }
                i--;
            }
        }else {
            while (j>=0){
                b=num2.charAt(j)-48;
                if(b+c>=10){
                    result=(b+c-10)+result;
                    c=1;
                }else {
                    result = b +c+ result;
                    c=0;
                }
                j--;
            }
        }
        if(c==0)return result;else return 1+result;
    }

    public boolean isUgly(int num) {
        if(num<=0){
            return false;
        }
        while (num%2==0){
            num=num/2;
        }
        while (num%3==0){
            num=num/3;
        }
        while (num % 5== 0) {
            num=num/5;
        }
        if(num==1)return true;
        else return false;
    }

    public boolean isPowerOfTwo(int n) {
        if(n==0)return false;
        while (n!=1){
            if((n&1)==1){
                return false;
            }else {
                n=n>>1;
            }
        }
        return true;
    }

    public String addBinary(String a, String b) {
        int len1=a.length();
        int len2=b.length();
        if(len1>len2){
            return addBinary(b,a);
        }else {
            int i=len1-1;
            int j=len2-1;
            int c=0;
            int n1;int n2;
            String result="";
            while (i>=0&&j>=0){
                n1=a.charAt(i)-'0';
                n2=b.charAt(j)-'0';
                if(n1+n2+c>=2){
                    result=n1+n2+c-2+result;
                    c=1;
                }else {
                    result=n1+n2+c+result;
                    c=0;
                }
                i--;j--;
            }
            while (j>=0){
                n2=b.charAt(j)-'0';
                if(n2+c>=2){
                    result=n2+c-2+result;
                    c=1;
                }else {
                    result = n2 +c+ result;
                    c=0;
                }
                j--;
            }
            if(c==0)return result;else return 1+result;
        }
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null&&q!=null&&p.val==q.val){
            if(isSameTree(p.left,q.left)&&isSameTree(p.right,q.right))
                return true;
            else return false;
        }else if(p==null&&q==null) {
            return true;
        }else {
                return false;
            }
        }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode p=head;
        if(head!=null){
            while (p!=null){
                ListNode q=p.next;
                while (q!=null&&p.val==q.val){
                    q=q.next;
                }
                p.next=q;
                p=p.next;
            }
            return head;
        }else {
            return head;
        }
    }

    public ListNode removeElements(ListNode head, int val) {
        while (head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null)return head;
        ListNode p=head;
        while (p!=null){
            ListNode q=p.next;
            while (q!=null&&q.val==val){
                q=q.next;
            }
            p.next=q;
            p=p.next;
        }
        return head;

    }

    public int searchInsert(int[] nums, int target) {
        int end=nums.length;
        for(int i=0;i<end;i++){
            if(nums[i]==target)return i;
            else if(nums[i]<target){
                continue;
            }else {
                return i-1;
            }
        }
        return end;
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        else {
            int temp=root.val;
            if(temp==sum&&root.right==null&&root.left==null) return true;
            else if(hasPathSum(root.left,sum-temp))return true;
            else if(hasPathSum(root.right,sum-temp)) return true;
            else return false;
        }
    }

    public int findMaxConsecutiveOnes(int[] nums) {
        int len=nums.length;
        int sum=0;
        int temp=0;
        for (int i=0;i<len;i++){
            if(nums[i]==1){
                temp++;
                sum=temp>sum?temp:sum;
            }else {
                temp=0;
            }
        }
        return sum;
    }

    public String convertToBase7(int num) {
        if(num<0){
            return "-"+convertToBase7(-num);
        }else {
            String result="";
            result=num%7+result;
            while (num/7!=0){
                num/=7;
                result=num%7+result;
            }
            return result;
        }
    }

    public int islandPerimeter(int[][] grid) {
        int height=grid.length;
        int len=grid[0].length;
        int sum=0;
        for (int i=0;i<height;i++){
            for(int j=0;j<len;j++){
                if(grid[i][j]==0) continue;
                else {
                    int count=4;
                    if(i-1>=0&&grid[i-1][j]==1)count--;
                    if(j-1>=0&&grid[i][j-1]==1)count--;
                    if(i+1<height&&grid[i+1][j]==1)count--;
                    if(j+1<len&&grid[i][j+1]==1)count--;
                    sum+=count;
                }
            }
        }
        return sum;
    }

    public boolean checkPerfectNumber(int num) {
        if(num==1) return false;
        int sum=1;
        int mid=(int)Math.sqrt(num);
        for (int i=2;i<=mid;i++){
            if(num%i==0){
                sum=sum+i+num/i;
            }
        }
        if(sum==num) return true;
        else return false;
    }

    public int[] twoSum(int[] numbers, int target) {
        int start=0;
        int end=numbers.length-1;
        int result[]=new int[2];
        while (start<end){
            int temp=numbers[start]+numbers[end];
            if(temp==target) {
                result[0]=start+1;
                result[1]=end+1;
                return result;
            }else if(temp<target){
                int t=numbers[start];
                start++;
                while (numbers[start]==t){
                    start++;
                }
            }else {
                int t=numbers[end];
                end--;
                while (numbers[end]==t){
                    end--;
                }
            }
        }
        return result;
    }

    public boolean isIsomorphic(String s, String t) {
        char []cs=s.toCharArray();
        char []ct=t.toCharArray();
        if(cs.length!=ct.length) return false;
        else {
            int len=cs.length;
            HashMap<Character,Character> map=new HashMap<>();
            char key,value;
            for(int i=0;i<len;i++){
                key=cs[i];
                if(map.containsKey(key)){
                    value=map.get(key);
                    if(value==ct[i])continue;
                    else return false;
                }else {
                    map.put(key,ct[i]);
                }
            }
            map.clear();
            for (int i=0;i<len;i++){
                key=ct[i];
                if(map.containsKey(key)){
                    value=map.get(key);
                    if(value==cs[i])continue;
                    else return false;
                }else {
                    map.put(key,cs[i]);
                }
            }
        }
        return true;
    }

    public String convertToTitle(int n) {
        if(n<=0) return null;
        else {
            String s="";
            char []temp={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R',
            'S','T','U','V','W','X','Y','Z'};
            while (n!=0){
                int t=(n-1)%26;
                s=temp[t]+s;
                n=(n-1)/26;
            }
            return s;
        }
    }

    public boolean isPowerOfFour(int num) {
        if(num<=0)return false;
        if(num==1)return true;
        while (num%4==0){
            num/=4;
            if(num==1||num==-1)return true;
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int len=nums.length;
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<len-1;i++){
            int key=nums[i];
            if(map.containsKey(key)){
                if(i-map.get(key)<=k)return true;
                else map.put(key,i);
            }else {
                map.put(key,i);
            }
        }
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null)return root;
        else if(root.right==null&&root.left==null)return root;
        else {
            TreeNode temp=root.left;
            root.left=root.right;
            root.right=temp;
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }
    }

    public int addDigits(int num) {
        if(num/10==0) return num;
        else {
            int sum=0;
            while (num%10!=0){
                sum+=num%10;
                num/=10;
            }
            return addDigits(sum);
        }
    }

    public boolean rotateString(String A, String B) {
        if(A.length()!=B.length()) return false;
        else {
            int len=A.length();
            if(A.equals(B)) return true;
            for (int i=0;i<len;i++){
                StringBuffer stringBuffer=new StringBuffer(A);
                stringBuffer.append(A.charAt(0));
                stringBuffer.deleteCharAt(0);
                A=stringBuffer.toString();
                if(A.equals(B)) return true;
            }
        }
        return false;
    }

    public char findTheDifference(String s, String t) {
        char[]cs=s.toCharArray();
        char[]ct=t.toCharArray();
        int len=cs.length;
        Arrays.sort(cs);
        Arrays.sort(ct);
        for (int i=0;i<len;i++){
            if(cs[i]!=ct[i])return ct[i];
        }
        return ct[len];
    }

    /**
     * 821字符的最短距离
     * @param S
     * @param C
     * @return
     */
    public int[] shortestToChar(String S, char C) {
        int index=S.indexOf(C);
        int []result=new int[S.length()];
        int mov=0;
        for (int i=0;i<=index;i++){
            result[i]=index-i;
        }
        while (index!=S.length()-1&&S.contains(C+"")){
            mov+=index+1;
            S=S.substring(index+1);
            index=S.indexOf(C);
            for (int i=0;i<=index;i++){
                int temp=(i+1)<(index-i)?(1+i):(index-i);
                result[mov+i]=temp;
            }
        }
        if(index==-1){
            for (int i=0;i<S.length();i++){
                result[mov+i]=i+1;
            }
        }
        return result;
    }

    /**
     * 832翻转图像
     * @param A
     * @return
     */
    public int[][] flipAndInvertImage(int[][] A) {
        int H=A.length;
        int W=A[0].length;
        int[][]result=new int[H][W];
        for (int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                result[i][j]=1-A[i][W-1-j];
            }
        }
        return result;
    }

    /**
     * 830 Positions of Large Groups
     * @param S
     * @return
     */
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> result=new ArrayList<>();
        char[] data=S.toCharArray();
        boolean[]map=new boolean[256];
        int len=data.length;
        int c=0;
        for (int i=0;i<len;i++){
            char d=data[i];
            if(map[d]){
                map=new boolean[256];
                while (i<len&&data[i]==d){
                    i++;
                }
                i--;
                if(i-c>=2){
                    List<Integer> node=new ArrayList<>();
                    node.add(c);
                    node.add(i);
                    result.add(node);
                }
            }else {
                map=new boolean[256];
                map[d]=true;
                c=i;
            }
        }
        return result;
    }

    /***
     * 824 Goat Latin
     * @param S
     * @return
     */
    public String toGoatLatin(String S) {
        StringBuffer s=new StringBuffer();
        String []strs=S.split(" ");
        int len=strs.length;
        for (int i=0;i<len;i++){
            char c=strs[i].charAt(0);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||
                    c=='A'||c=='E'||c=='I'||c=='O'||c=='U'){
                s.append(strs[i]).append("ma");
                for(int j=0;j<i+1;j++){
                    s.append('a');
                }
                s.append(" ");
            }else {
                s.append(strs[i].substring(1)).append(strs[i].charAt(0)).append("ma");
                for(int j=0;j<i+1;j++){
                    s.append('a');
                }
                s.append(" ");
            }
        }
        return s.substring(0,s.length()-1);
    }

    /**
     * 819 最常见单词
     * @param paragraph
     * @param banned
     * @return
     */
    public String mostCommonWord(String paragraph, String[] banned) {
        String []str=paragraph.toLowerCase().split("[ |\\?|!|'|\\,|;|.]");
        int len=str.length;
        Map<String,Integer> map=new HashMap<>();
        String result="";int max=0;
        int len2=banned.length;
        for(int i=0;i<len;i++){
            String s=str[i];
            if(s.equals(""))continue;
            int j=0;
            for (j=0;j<len2;j++){
                if(s.equalsIgnoreCase(banned[j])){
                    break;
                }
            }
            if(j!=len2)continue;
            else if(map.containsKey(s)){
                int temp=map.get(s)+1;
                map.put(s,temp);
                if(max<temp){
                    max=temp;
                    result=s;
                }
            }else {
                map.put(s,1);
                if(max<1){
                    max=1;
                    result=s;
                }
            }
        }
        return result;
    }

    /**
     * 693交替位二进制数
     * @param n
     * @return
     */
    public boolean hasAlternatingBits(int n) {
        int c=n&1;
        n=n>>1;
        while (n!=0){
            if((n&1)==c)return false;
            else {
                c=n&1;
                n=n>>1;
            }
        }
        return true;
    }

    /**
     * 804唯一摩斯密码词
     * @param words
     * @return
     */
    public int uniqueMorseRepresentations(String[] words) {
        String[]code={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        int len=words.length;
        Map<String,Integer> codemap=new HashMap<>();
        int count=0;
        for (int i=0;i<len;i++){
            String s=words[i];
            int slen=s.length();
            StringBuffer sb=new StringBuffer();
            for (int j=0;j<slen;j++){
                sb.append(code[s.charAt(j)-'a']);
            }
            s=sb.toString();
            if(codemap.containsKey(s)){

            }else {
                count++;
                codemap.put(s,0);
            }
        }
        return count;
    }

    /**
     * 806写字符串需要的行数
     * @param widths
     * @param S
     * @return
     */
    public int[] numberOfLines(int[] widths, String S) {
        int len=S.length();
        int row=1;
        int sum=0;
        for(int i=0;i<len;i++){
            int temp=widths[S.charAt(i)-'a'];
            sum+=temp;
            if(sum>100){
                row++;
                sum=temp;
            }
        }
        int res[]={row,sum};
        return res;
    }

    /**
     * 788旋转数字
     * @param N
     * @return
     */
    public int rotatedDigits(int N) {
        int res=0;
        for (int i=1;i<=N;i++){
            res+=getOne(i);
        }
        return res;
    }
    private int getOne(int i) {
        boolean change=false;
        while (i!=0){
            int mod=i%10;
            if(mod==2||mod==5||mod==6||mod==9){
                change=true;
                i=i/10;continue;
            }else if(mod==3||mod==4||mod==7){
                return 0;
            }else {
                i/=10;
                continue;
            }
        }
        if(change) return 1;
        else return 0;
    }

    /**
     * 至少是其他数字的两倍
     * @param nums
     * @return
     */
    public int dominantIndex(int[] nums) {
        int len=nums.length;
        if(len==1) return nums[0];
        else {
            int max,j;
            if(nums[0]>nums[1]){
                max=nums[0];j=0;
            }else {
                max=nums[1];j=1;
            }
            for (int i=0;i<len;i++){
                if(i==j) continue;
                else {
                    if(nums[i]*2<=max)continue;
                    else {
                        int k=i;
                        for(;k<len;k++){
                            if(nums[k]>=max*2){
                                max=nums[k];
                                j=k;
                                i--;break;
                            }
                        }
                        if(k==len)
                            return -1;
                    }
                }
            }
            return j;
        }
    }

    /**
     * 728自除数
     * @param left
     * @param right
     * @return
     */
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> res=new ArrayList<>();
        for(int i=left;i<=right;i++){
            if(isDividingNumber(i)){
                res.add(i);
            }
        }
        return res;
    }
    private boolean isDividingNumber(int num) {
        int i=num;
        while (i!=0){
            int mod=i%10;
            if(mod==0)return false;
            if(num%mod==0){
                i=i/10;
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

    /**
     * 107二叉树的层次遍历II
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> l=new ArrayList<List<Integer>>();
        addLevel(l,0,root);
        Collections.reverse(l);
        return l;
    }
    public void addLevel(List<List<Integer>> list, int level, TreeNode node){
        if(node==null)return ;
        if(list.size()-1<level)list.add(new ArrayList<Integer>());
        list.get(level).add(node.val);

        addLevel(list,level+1,node.left);
        addLevel(list,level+1,node.right);
    }

    /**
     * 119杨辉三角
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> data=new ArrayList<>();
        if(rowIndex<=0)return data;
        else {
            data.add(1);
            for (int i=2;i<=rowIndex;i++){
                for(int j=i-1;j>1;j--){
                    data.set(j-1,data.get(j-1)+data.get(j-2));
                }
                data.add(1);
            }
            return data;
        }
    }

    /**
     * 345反转字符串中的元音字母
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        char[]data=s.toCharArray();
        int len=data.length;
        int i=0,j=len-1;
        while (i<j){
            for (;i<j;i++){
                char c=data[i];
                if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'
                        ||c=='A'||c=='E'||c=='I'||c=='O'||c=='U'){
                    break;
                }
            }
            for (;j>i;j--){
                char c=data[j];
                if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'
                        ||c=='A'||c=='E'||c=='I'||c=='O'||c=='U'){
                    break;
                }
            }
            char temp=data[j];
            data[j]=data[i];
            data[i]=temp;
            i++;
            j--;
        }
        StringBuffer sb=new StringBuffer();
        for(int k=0;k<len;k++){
            sb.append(data[k]);
        }
        return sb.toString();
    }

    /**
     * 有效的完全平方数
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        for(int i=0;i<num;i++){
            if(i*i==num)return true;
            else if((num-i*i)<(2*i+1)) return false;
        }
        return false;
    }

    /**
     * 111二叉树的最小深度
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        else if(root.right!=null&&root.left==null) return 1+minDepth(root.right);
        else if(root.left!=null&&root.right==null) return 1+minDepth(root.left);
        else if(root.left==null&&root.right==null) return 1;
        else {
            int left=minDepth(root.left);
            int right=minDepth(root.right);
            return 1+(left<right?left:right);
        }
    }

    /**
     * 434字符串中的单词数
     * @param s
     * @return
     */
    public int countSegments(String s) {
        String []str=s.split(" ");
        int len=str.length,res=0;
        for (int i=0;i<len;i++){
            if(str[i].equals(""));
            else {
                res++;
            }
        }
        return res;
    }

    /**
     * 476数字的补数
     * @param num
     * @return
     */
    public int findComplement(int num) {
        int level=1;
        int sum=0;
        while (num!=0){
            int temp=num%2;
            num=num/2;
            sum+=(1-temp)*level;
            level<<=1;
        }
        return sum;
    }

    /**
     * 575分糖果
     * @param candies
     * @return
     */
    public int distributeCandies(int[] candies) {
        Arrays.sort(candies);
        if(candies.length<=0)return 0;
        else {
            int kind=1;
            int len=candies.length;
            int temp=candies[0];
            for (int i=1;i<len;i++){
                if(candies[i]!=temp){
                    temp=candies[i];
                    kind++;
                }
            }
            if(kind*2>=len)return len/2;
            else {
                return kind;
            }
        }
    }

    /**
     * 633平方数之和
     * @param c
     * @return
     */
    public boolean judgeSquareSum(int c) {
        int temp=(int)Math.sqrt(c);
        for (int i=0,j=temp;i<=j;){
            int minus=c-i*i;
            if(minus==j*j) return true;
            else if(minus<j*j) j--;
            else i++;
        }
        return false;
    }

    /**
     * 500键盘行
     * @param words
     * @return
     */
    public String[] findWords(String[] words) {
        Map<Character,Integer> map=new HashMap<>();
        map.put('q',1);map.put('Q',1);map.put('E',1);map.put('e',1);map.put('r',1);map.put('R',1);map.put('t',1);map.put('T',1);map.put('w',1);map.put('W',1);
        map.put('y',1);map.put('Y',1);map.put('u',1);map.put('U',1);map.put('i',1);map.put('I',1);map.put('o',1);map.put('O',1);map.put('p',1);map.put('P',1);
        map.put('a',2);map.put('A',2);map.put('s',2);map.put('S',2);map.put('d',2);map.put('D',2);map.put('f',2);map.put('F',2);map.put('g',2);
        map.put('G',2);map.put('h',2);map.put('H',2);map.put('j',2);map.put('J',2);map.put('k',2);map.put('K',2);map.put('l',2);map.put('L',2);
        map.put('z',3);map.put('Z',3);map.put('x',3);map.put('X',3);map.put('c',3);map.put('C',3);map.put('v',3);map.put('V',3);
        map.put('b',3);map.put('B',3);map.put('n',3);map.put('N',3);map.put('m',3);map.put('M',3);
        int len1=words.length;
        ArrayList<String> res=new ArrayList<>();
        for(int i=0;i<len1;i++){
            char[]str=words[i].toCharArray();
            int len2=str.length;
            int j=0;
            if(len2==0){
                res.add(words[i]);
                break;
            }else {
                if(!map.containsKey(str[0]))continue;;
                int level=map.get(str[0]);
                for(;j<len2;j++){
                    if(!map.containsKey(str[j]))break;
                    if(map.get(str[j])!=level)break;
                }
                if(j==len2){
                    res.add(words[i]);
                }
            }
        }
        int size=res.size();
        String[]r=new String[size];
        Iterator<String> iterator=res.iterator();
        int i=0;
        while (iterator.hasNext()){
            r[i]=iterator.next();
            i++;
        }
        return r;
    }

    /**
     * 812最大三角形面积
     * @param points
     * @return
     */
    public double largestTriangleArea(int[][] points) {
        int len=points.length;
        double max=Double.MIN_VALUE;
        if(len<3) return 0;
        else {
            for(int i=0;i<len-2;i++){
                for (int j=i+1;j<len-1;j++){
                    for (int k=j+1;k<len;k++){
                        double a=getdistance(points[i],points[j]);
                        double b=getdistance(points[i],points[k]);
                        double c=getdistance(points[j],points[k]);
                        double p=(a+b+c)/2;
                        double temp=p*(p-a)*(p-b)*(p-c);
                        if(temp>max) max=temp;
                    }
                }
            }
        }
        return Math.sqrt(max);
    }
    private double getdistance(int[]a,int b[]){
        int temp=(a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]);
        return Math.sqrt(temp);
    }

    /**
     * 771宝石与石头
     * @param J
     * @param S
     * @return
     */
    public int numJewelsInStones(String J, String S) {
        char[]data=S.toCharArray();
        int len=data.length;
        char[]table=new char[256];
        for(int i=0;i<len;i++){
            table[data[i]]++;
        }
        int sum=0;
        char[]Js=J.toCharArray();
        len=Js.length;
        for(int i=0;i<len;i++){
            sum+=table[Js[i]];
        }
        return sum;
    }

    /**
     * 762二进制表示中质数个计算置位
     * @param L
     * @param R
     * @return
     */
    public int countPrimeSetBits(int L, int R) {
        int count=0;
        for(int i=L;i<=R;i++){
            int n=i;
            int time=0;
            while (n!=0){
                if(n%2==1) time++;
                n=n/2;
            }
            if(time==2||time==3||time==5||time==7||time==11||time==13||time==17||time==19){
                count++;
            }
        }
        return count;
    }

    /**
     * 766托普利茨矩阵
     * @param matrix
     * @return
     */
    public boolean isToeplitzMatrix(int[][] matrix) {
        int H=matrix.length;
        int W=matrix[0].length;
        for (int i=0;i<W-1;i++){
            int line=0;
            int mov=i;
            int temp=matrix[line][mov];
            mov++;
            line++;
            while (mov<W&&line<H){
                if(matrix[line][mov]!=temp) return false;
                mov++;line++;
            }
        }
        for (int i=1;i<H-1;i++){
            int line=i,mov=0;
            int temp=matrix[line][mov];
            line++;
            mov++;
            while (mov<W&&line<H){
                if(matrix[line][mov]!=temp) return false;
                mov++;line++;
            }
        }
        return true;
    }

    /**
     * 724寻找数组中心索引
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        int len=nums.length;
        if(len<=2)return -1;
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
        }
        int temp=0;
        int i=0;
        while (i<len){
            if(sum-temp-nums[i]==temp) return i;
            else {
                temp+=nums[i];
                i++;
            }
        }
        return -1;
    }

    /**
     * 744寻找比目标字母大的最小字母
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        int len=letters.length;
        if(len==1)return letters[0];
        if(target>letters[len-1]) return letters[0];
        for (int i=0;i<len;i++){
            if(target>=letters[i])continue;
            else {
                return letters[i];
            }
        }
        return letters[0];
    }

    /**
     * 733图像渲染
     * @param image
     * @param sr
     * @param sc
     * @param newColor
     * @return
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int H=image.length;int W=image[0].length;
        boolean [][]isPaint=new boolean[H][W];
        floodFillOne(image,sr,sc,newColor,isPaint);
        return image;
    }
    private void floodFillOne(int[][] image, int sr, int sc, int newColor, boolean[][] isPaint) {
        isPaint[sr][sc]=true;
        int color=image[sr][sc];
        image[sr][sc]=newColor;
        int H=image.length;int W=image[0].length;
        if(sr-1>=0&&!isPaint[sr-1][sc]&&image[sr-1][sc]==color){
            floodFillOne(image,sr-1,sc,newColor,isPaint);
        }
        if(sc-1>=0&&!isPaint[sr][sc-1]&&image[sr][sc-1]==color){
            floodFillOne(image,sr,sc-1,newColor,isPaint);
        }
        if(sr+1<H&&!isPaint[sr+1][sc]&&image[sr+1][sc]==color){
            floodFillOne(image,sr+1,sc,newColor,isPaint);
        }
        if(sc+1<W&&!isPaint[sr][sc+1]&&image[sr][sc+1]==color){
            floodFillOne(image,sr,sc+1,newColor,isPaint);
        }
        int []a[]=new int[10][];

    }

    /**
     * 849到最近的人的最大距离
     * @param seats
     * @return
     */
    public int maxDistToClosest(int[] seats) {
        int len=seats.length;
        int i=0;
        while (i<len&&seats[i]!=1){
            i++;
        }
        int max=i;
        int j=i+1;
        while (j<len){
            if(seats[j]==1){
                int temp=j+i;
                temp=temp/2;
                temp=temp-i;
                if(max>temp){

                }else {
                    max=temp;
                }
                i=j;j++;
            }else {
                j++;
            }
        }
        if(seats[len-1]!=1){
            int temp=len-1-i;
            max=max>temp?max:temp;
        }
        return max;
    }

    /**
     * 844比较含退格的字符串
     * @param S
     * @param T
     * @return
     */
    public boolean backspaceCompare(String S, String T) {
        Stack<Character> stack1=new Stack<>();
        Stack<Character> stack2=new Stack<>();
        char []cs=S.toCharArray();
        char []ct=T.toCharArray();
        for(int i=0;i<cs.length;i++){
            if(cs[i]=='#'){
                if(!stack1.isEmpty()){
                    stack1.pop();
                }
            }
            else {
                stack1.push(cs[i]);
            }
        }
        for(int i=0;i<ct.length;i++){
            if(ct[i]=='#'){
                if(!stack2.isEmpty()){
                    stack2.pop();
                }
            }
            else {
                stack2.push(ct[i]);
            }
        }
        if(stack1.size()!=stack2.size())return false;
        while (!stack1.isEmpty()){
            if(stack1.pop()!=stack2.pop())return false;
        }
        return true;
    }

    /**
     * 840矩阵中的幻方
     * @param grid
     * @return
     */
    public int numMagicSquaresInside(int[][] grid) {
        int num=0;
        int len=grid[0].length;
        int height=grid.length;
        if(len<3||height<3){
            return 0;
        }
        for(int i=0;i<=len-3;i++){
            for (int j=0;j<=height-3;j++){
                if(isMagicSquaresInside(j,i,grid)){
                    num++;
                }
            }
        }
        return num;
    }
    private boolean isMagicSquaresInside(int i, int j, int[][] grid) {
        for(int a=i;a<i+3;a++){
            for(int b=j;b<j+3;b++){
                if(grid[a][b]>=10||grid[a][b]==0)return false;
            }
        }
        int sum=grid[i][j]+grid[i][j+1]+grid[i][j+2];
        if(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2]!=sum){
            return false;
        }
        if(grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]!=sum){
            return false;
        }
        if(grid[i][j]+grid[i+1][j]+grid[i+2][j]!=sum){
            return false;
        }
        if(grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1]!=sum){
            return false;
        }
        if(grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2]!=sum){
            return false;
        }
        if(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]!=sum){
            return false;
        }
        if(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]!=sum){
            return false;
        }
        return true;
    }

    /**
     * 836矩阵重叠
     * @param rec1
     * @param rec2
     * @return
     */
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        int x11=rec1[0],y11=rec1[1],x12=rec1[2],y12=rec1[3];
        int x21=rec2[0],y21=rec2[1],x22=rec2[2],y22=rec2[3];
        boolean flag=false;
        if(x21>=x12) flag=false;
        else if(x22<=x11) flag=false;
        else if(y21>=y12) flag=false;
        else if(y22<=y11) flag=false;
        else flag=true;
        return flag;
    }

    /**
     * 811子域名访问计数
     * @param cpdomains
     * @return
     */
    public List<String> subdomainVisits(String[] cpdomains) {
        HashMap<String,Integer> map=new HashMap<>();
        int len=cpdomains.length;
        for(int i=0;i<len;i++){
            int temp=Integer.valueOf(cpdomains[i].split(" ")[0]);
            String ss=cpdomains[i].split(" ")[1];
            while (ss.contains(".")){
                if(map.containsKey(ss)){
                    int num=map.get(ss);
                    map.put(ss,num+temp);
                }else {
                    map.put(ss,temp);
                }
                int index=ss.indexOf(".");
                ss=ss.substring(index+1);
            }
            if(map.containsKey(ss)){
                int num=map.get(ss);
                map.put(ss,num+temp);
            }else {
                map.put(ss,temp);
            }
            int index=ss.indexOf(".");
            ss=ss.substring(index+1);
        }
        List<String> strings=new ArrayList<>();
        Set<String> set=map.keySet();
        Iterator<String> iterator=set.iterator();
        while (iterator.hasNext()){
            String s=iterator.next();
            int temp=map.get(s);
            strings.add(temp+" "+s);
        }
        return strings;
    }

    /**
     * 110平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int temp=treeHeight(root.left)-treeHeight(root.right);
        if(temp<-1||temp>1)return false;
        else {
            if(isBalanced(root.left)&&isBalanced(root.right)) return true;
            else return false;
        }
    }
    public int treeHeight(TreeNode root){
        if(root==null) return 0;
        else if(root.left==null&&root.right==null) return 1;
        else {
            return 1+Math.max(treeHeight(root.left),treeHeight(root.right));
        }
    }

    /**
     * 190颠倒二进制位
     * @param n
     * @return
     */
    public int reverseBits(int n) {
        StringBuffer strb=new StringBuffer();
        for(int i=0;i<32;i++){
            strb.append(n%2);
            n = n >>> 1;
        }
        if(strb.toString().equals(""))return 0;
        int res=0;
        for(int i=0;i<32;i++){
            res=res*2+strb.charAt(i)-'0';
        }
        return res;
    }

    /**
     * 235二叉搜索树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val>q.val){
            return lowestCommonAncestor(root,q,p);
        }
        else {
            if(root.val>=p.val&&root.val<=q.val) return root;
            else if(root.val>q.val) return lowestCommonAncestor(root.left,p,q);
            else return lowestCommonAncestor(root.right,p,q);
        }
    }

    /**
     * 383赎金信
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int[]data=new int[256];
        int len1=ransomNote.length();
        for(int i=0;i<len1;i++){
            data[ransomNote.charAt(i)]++;
        }
        int len2=magazine.length();
        int []data2=new int[256];
        for(int i=0;i<len2;i++){
            data2[magazine.charAt(i)]++;
        }
        for(int i=0;i<256;i++){
            if(data[i]==0)continue;
            else {
                if(data[i]>data2[i])return false;
            }
        }
        return true;
    }

    /**
     * 400第N个数字
     * @param n
     * @return
     */
    public int findNthDigit(int n) {
        long num=9;int digits=1;
        while (n-digits*num>0){
            n-=digits*num;
            digits++;
            num*=10;
        }
        int mov=n/digits;
        long cur=num/9-1;
        cur=cur+mov;
        int mod=n%digits;
        if(mod==0){
            return (int)(cur%10);
        }else {
            cur++;
            mod=digits-mod;
            int res=0;
            for(int i=0;i<=mod;i++){
                res=(int)(cur%10);
                cur/=10;
            }
            return res;
        }
    }

    /**
     * 405数字转换为十六进制数
     * @param num
     * @return
     */
    public String toHex(int num) {
        if(num==0)return "0";
        String temp[]={"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};
        String res="";
        int count=0;
        while (num!=0&&count<8){
            int i=num&0xf;
            res=temp[i]+res;
            num=num>>4;
            count++;
        }
        return res;
    }

    /**
     * 409最长回文串
     * @param s
     * @return
     */
    public int longestPalindrome(String s) {
        System.out.println(s.length());
        int data[]=new int[256];
        for (char c:s.toCharArray()
             ) {
            data[c]++;
        }
        int odd=0;
        int sum=0;
        for(int i=0;i<256;i++){
            int temp=data[i];
            if(temp%2==0){
                sum+=temp;
            }else {
                odd=temp;
                sum+=temp-1;
            }
        }
        if(odd!=0){
            sum+=1;
        }
        return sum;
    }

    /**
     * 852山脉数组的封顶索引
     * @param A
     * @return
     */
    public int peakIndexInMountainArray(int[] A) {
        int len=A.length;
        int i=1;
        for(i=1;i<len-1;i++){
            if(A[i-1]<A[i]&&A[i]>A[i+1])break;
        }
        return i;
    }

    /**
     * 783二叉搜索树结点最小距离
     * @param root
     * @return
     */
    public int minDiffInBST(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        list=minDiffInBSTOne(root,list);
        Collections.sort(list);
        Iterator<Integer> iterator=list.iterator();
        int first=iterator.next();
        int second=iterator.next();
        int min=Math.abs(first-second);
        while (iterator.hasNext()){
            first=second;
            second=iterator.next();
            int temo=Math.abs(first-second);
            min=min<temo?min:temo;
        }
        return min;
    }
    private List<Integer> minDiffInBSTOne(TreeNode root, List<Integer> list) {
        if(root!=null){list.add(root.val);
        list=minDiffInBSTOne(root.left,list);
        list=minDiffInBSTOne(root.right,list);}
        return list;
    }

    /**
     * 717 1比特与2比特字符
     * @param bits
     * @return
     */
    public boolean isOneBitCharacter(int[] bits) {
        int len=bits.length;
        int flag=-1;
        for(int i=0;i<len;i++){
            if(bits[i]==1){
                flag=2;i++;
            }else {
                flag=1;
            }
        }
        if(flag==1)return true;
        else return false;
    }

    /**
     * 492构造矩形
     * @param area
     * @return
     */
    public int[] constructRectangle(int area) {
        int n=(int)Math.sqrt(area);
        for(;n>0;n--){
            if(area%n==0){
                int []res=new int[2];
                res[0]=n;
                res[1]=area/n;
                return res;
            }
        }
        return null;
    }

    /**
     * 657判断路线成圈
     * @param moves
     * @return
     */
    public boolean judgeCircle(String moves) {
        int i=0,j=0;
        char[]data=moves.toCharArray();
        int len=data.length;
        for(int a=0;a<len;a++){
            switch (data[a]){
                case 'U':
                    j++;break;
                case 'D':
                    j--;break;
                case 'L':
                    i--;break;
                case 'R':
                    i++;break;
                default:
                    break;
            }
        }
        if(i==0&&j==0){
            return true;
        }else return false;
    }

    /**
     * 868转置矩阵
     * @param A
     * @return
     */
    public int[][] transpose(int[][] A) {
        int H=A.length;
        int W=A[0].length;
        int [][]res=new int[W][H];
        for(int i=0;i<H;i++){
            for(int j=i;j<W;j++){
                res[j][i]=A[i][j];
            }
        }
        return res;
    }

    /**
     * 860柠檬水找零
     * @param bills
     * @return
     */
    public boolean lemonadeChange(int[] bills) {
        int data[]=new int[3];
        int len=bills.length;
        for(int i=0;i<len;i++){
            int temp=bills[i];
            if(temp==5){
                data[0]++;
            }else if(temp==10){
                data[0]--;
                data[1]++;
            }else if(temp==20){
                data[2]++;
                if(data[1]>0){
                    data[1]--;
                }else {
                    data[0]--;
                    data[0]--;
                }
                data[0]--;
            }
            if(data[0]<0)return false;
        }
        return true;
    }

    /**
     * 859亲密字符串
     * @param A
     * @param B
     * @return
     */
    public boolean buddyStrings(String A, String B) {
        char[] cA=A.toCharArray();
        char[] cB=B.toCharArray();
        int len=cA.length;

        if(len!=cB.length)return false;
        if(len<2)return  false;
        StringBuffer sb=new StringBuffer(B);
        if(sb.reverse().toString().equals(A)) return true;
        else {
            int data[]={-1,-1,0};
            int change=0;
            for(int i=0;i<len;i++){
                if(cA[i]==cB[i])continue;
                else {
                    data[change]=i;
                    change++;
                    if(change>=3)return false;
                }
            }
            if(data[0]==data[1]){
                char[] c=new char[26];
                for(int i=0;i<len;i++){
                    int t=cA[i]-'a';
                    c[t]++;
                    if(c[t]>=2) return true;
                }
                return false;
            }

            if(cA[data[0]]==cB[data[1]]&&cA[data[1]]==cB[data[0]])return true;
            else return false;
        }
    }

    /**
     * 447回旋镖数量
     * @param points
     * @return
     */
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;//点的个数
        int[][] lens = new int[n][n];//点与点之间的距离
        int temp = 0;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                temp = (int) (Math.pow(points[i][0]-points[j][0],2)+Math.pow(points[i][1]-points[j][1],2));
                lens[i][j] = temp;
                lens[j][i] = temp;
            }
        }
        //从第一个点开始
        int sum = 0;
        for(int i = 0;i<n;i++){
            Map<Integer,Integer> map = new HashMap<>();
            for(int j = 0;j<n;j++){
                if(j==i)
                    continue;
//                System.out.println("i:"+i+" j:"+j+"  "+lens[i][j]);
                if(map.containsKey(lens[i][j])){
                    map.put(lens[i][j],map.get(lens[i][j]).intValue()+1);
                }else{
                    map.put(lens[i][j],1);
                }
            }
            int count = 0;
            for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
                count = entry.getValue();
                if(count>=2){
                    sum+=(count)*(count-1);
                }
            }
        }
        return sum;
    }

    /**
     * 448找到所有 数组中消失的数字
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res=new ArrayList<>();
        Arrays.sort(nums);
        int len=nums.length;
        for(int i=0;i<len;i++){
            if(nums[i]!=nums[nums[i]-1]) {
                int temp = nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=temp;
                i--;
            }
        }
        for(int i=0;i<len;i++){
            if(nums[i]!=i+1) res.add(i+1);
        }
        return res;
    }

    /**
     * 455分发饼干
     * @param g
     * @param s
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count=0;
        int len1=g.length,len2=s.length;
        int i=0,j=0;
        for(;i<len1;i++){
            for(;j<len2;j++){
                if(g[i]<=s[j]){
                    count++;break;
                }
            }
        }
        return count;
    }

    /**
     * 459重复的子字符串
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {
        int len=s.length();
        if(len<2) return false;
        int temp=len/2;
        while (temp>0){
            if(len%temp!=0){
                temp--;
                continue;
            }else {
                String t=s.substring(0,temp);
                int i=0;
                while (i<len){
                    if(s.substring(i,i+temp).equals(t)){
                        i+=temp;
                    }else {
                        break;
                    }
                }
                if(i==len) return true;
                temp--;
            }
        }
        return false;
    }

    /**
     * 443压缩字符串
     * @param chars
     * @return
     */
    public int compress(char[] chars) {
        int len=chars.length;
        int cur=0;
        for(int i=0;i<len;i++){
            char c=chars[i];
            int j=i+1;
            while (j<len&&chars[j]==c){
                j++;
            }
            if(j-i==1){
                chars[cur]=chars[i];
                cur++;
            }else {
                chars[cur]=chars[i];
                cur++;
                String s=String.valueOf(j-i);
                char[]temp=s.toCharArray();
                for(int k=0;k<temp.length;k++){
                    chars[cur]=temp[k];
                    cur++;
                }
            }
            i=j-1;
        }
        for(int i=0;i<len;i++){
            System.out.print(chars[i]);
        }
        System.out.println();
        return cur;
    }

    /**
     * 661图片平滑器
     * @param M
     * @return
     */
    public int[][] imageSmoother(int[][] M) {
        int H=M.length;
        int W=M[0].length;
        int[][]res=new int[H][W];
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                int a0=M[i][j];int mount=1;
                if((i-1)>=0&&(j-1)>=0){
                    a0+=M[i-1][j-1];
                    mount++;
                }
                if((i-1)>=0){
                    a0+=M[i-1][j];
                    mount++;
                }
                if((i-1)>=0&&(j+1)<W){
                    a0+=M[i-1][j+1];
                    mount++;
                }
                if(j-1>=0){
                    a0+=M[i][j-1];
                    mount++;
                }
                if(j+1<W){
                    a0+=M[i][j+1];
                    mount++;
                }
                if((i+1)<H&&(j-1)>=0){
                    a0+=M[i+1][j-1];
                    mount++;
                }
                if((i+1)<H){
                    a0+=M[i+1][j];
                    mount++;
                }
                if((i+1)<H&&(j+1)<W){
                    a0+=M[i+1][j+1];
                    mount++;
                }
                res[i][j]=a0/mount;
            }
        }
        return res;
    }

    /**
     * 441排列硬币
     * @param n
     * @return
     */
    public int arrangeCoins(int n) {
        int res=0;
        while (n>=res){
            n=n-res;
            res++;
        }
        return --res;
    }

    /**
     * 475供暖器
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius(int[] houses, int[] heaters) {
        int res=0;
        int len1=houses.length;
        int len2=heaters.length;
        for(int i=0;i<len1;i++){
            int temp=Math.abs(heaters[0]-houses[i]);
            for(int j=1;j<len2;j++){
                int t=Math.abs(heaters[j]-houses[i]);
                temp=temp<t?temp:t;
            }
            res=res>temp?res:temp;
        }
        return res;
    }

    /**
     * 479最大回文数乘积
     * @param n
     * @return
     */
    public int largestPalindrome(int n) {
        int upper=(int)Math.pow(10,n)-1,lower=upper/10;
        for(int i=upper;i>lower;i--){
            String t=String.valueOf(i);
            StringBuffer sb=new StringBuffer(t);
            t=t+sb.reverse();
            long l=Long.parseLong(t);
            for(long j=upper;j*j>l;j--){
                if(l%j==0){
                    return (int)(l%1337);
                }
            }
        }
        return 9;
    }

    /**
     * 482密钥格式化
     * @param S
     * @param K
     * @return
     */
    public String licenseKeyFormatting(String S, int K) {
        char c[]=S.toUpperCase().toCharArray();
        StringBuilder sb=new StringBuilder();
        int len=c.length;
        int i=len-1;

        while (i>=0){
            for(int j=0;(i>=0)&&j<K;j++){
                if(c[i]=='-'){
                    j--;
                }else {
                    sb.append(c[i]);
                }
                i--;
            }
            sb.append("-");
        }
        String res=sb.reverse().toString();
        len=res.length();
        int index=0;
        while (i<len&&res.charAt(index)=='-'){
            index++;
        }
        return res.substring(index);
    }

    /**
     * 520检测大写字母
     * @param word
     * @return
     */
    public boolean detectCapitalUse(String word) {
        int len=word.length();
        if(len<=1){
            return true;
        }else {
            char c=word.charAt(0);
            String less=word.substring(1);
            if(c>='a'&&c<='z'){
                if(less.equals(word.substring(1).toLowerCase())){
                    return true;
                }else {
                    return false;
                }
            }else if(c>='A'&&c<='Z'){
                if(less.equals(word.substring(1).toLowerCase())||less.equals(word.substring(1).toUpperCase())){
                    return true;
                }else {
                    return false;
                }
            }else {
                return false;
            }
        }
    }

    /**
     * 257二叉树的所有路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res=new ArrayList<>();
        if(root==null) return res ;
        List<Integer> node=new ArrayList<>();
        binaryTreePathOne(res,node,root);
        return res;
    }
    private void binaryTreePathOne(List<String> res, List<Integer> node, TreeNode root) {
        int size=node.size();
        node.add(root.val);
        if(root.left==null&&root.right==null){
            Iterator<Integer> iterator=node.iterator();
            String s="";
            while (iterator.hasNext()){
                s+="->"+iterator.next();
            }
            res.add(s.substring(2));
        }
        if(root.left!=null){
            binaryTreePathOne(res,node,root.left);
        }
        if(root.right!=null){
            binaryTreePathOne(res,node,root.right);
        }
        node.remove(size);
    }

    /**
     * 290单词模式
     * @param pattern
     * @param str
     * @return
     */
    public boolean wordPattern(String pattern, String str) {
        char[]p=pattern.toCharArray();
        String []s=str.split(" ");
        int len=p.length;
        if(len!=s.length){
            return false;
        }
        Map<String,Character> map=new HashMap<>();
        for(int i=0;i<len;i++){
            if(map.containsKey(s[i])){
                if(p[i]==map.get(s[i]));
                else return false;
            }else {
                map.put(s[i],p[i]);
            }
        }
        Map<Character,String> map2=new HashMap<>();
        for(int i=0;i<len;i++){
            if(map2.containsKey(p[i])){
                if(s[i].equals(map2.get(p[i])));
                else return false;
            }else {
                map2.put(p[i],s[i]);
            }
        }
        return true;
    }

    /**
     * 349两个数组的交集
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len1=nums1.length;
        int len2=nums2.length;
        List<Integer> list=new ArrayList<>();
        int i=0,j=0;
        while (i<len1&&j<len2){
            int a=nums1[i],b=nums2[j];
            if(a==b){
                if(list.contains(a)){i++;j++;continue;}
                else {
                    list.add(a);i++;j++;
                }
            }else if(a<b){
                i++;
            }else j++;
        }
        int res[]=new int[list.size()];
        Iterator<Integer> iterator=list.iterator();
        i=0;
        while (iterator.hasNext()){
            res[i]=iterator.next();i++;
        }
        return res;
    }

    /**
     * 404左叶子之和
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null) return 0;
        return sumOfLeaves(root.left,1)+sumOfLeaves(root.right,2);
    }
    private int sumOfLeaves(TreeNode root, int i) {

        int sum=0;
        if(root==null) return 0;
        else if(root.left==null&&root.right==null){
            if(i==1) return root.val;
            else return 0;
        }
        if(root.left!=null){
            sum+=sumOfLeaves(root.left,1);
        }
        if(root.right!=null){
            sum+=sumOfLeaves(root.right,2);
        }
        return sum;
    }

    /**
     * 437路径总和III
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {
        if(root==null)return 0;
        return pathOneSum(root,sum,0)+pathSum(root.left,sum)+pathSum(root.right,sum);
    }
    private int pathOneSum(TreeNode root, int sum,int already) {
        if(root==null){
            return 0;
        }
        already+=root.val;
        int s=0;
        if(already==sum){
            s=1;
        }
        return s+pathOneSum(root.left,sum,already)+pathOneSum(root.right,sum,already);
    }

    /**
     * 453最小移动次数使数组元素相等
     * @param nums
     * @return
     */
    public int minMoves(int[] nums) {
        int min=Integer.MAX_VALUE,len=nums.length;
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
            min=min<nums[i]?min:nums[i];
        }
        return sum-min*len;
    }

    /**
     * 784字母大小写的全排列
     * @param S
     * @return
     */
    public List<String> letterCasePermutation(String S) {
        List<String> res=new ArrayList<>();
        S=S.toLowerCase();
        String s="";
        char[]c=S.toCharArray();
        letterCasePermutationOne(res,s,c,0);
        return res;
    }
    private void letterCasePermutationOne(List<String> res, String s, char[] c, int i) {
        if(i>=c.length){
            res.add(s);
            return;
        }
        char temp=c[i];
        if(temp>='0'&&temp<='9'){
            s+=temp;
            letterCasePermutationOne(res,s,c,i+1);
        }else {
            letterCasePermutationOne(res,s+temp,c,i+1);
            temp=Character.toUpperCase(temp);
            letterCasePermutationOne(res,s+temp,c,i+1);
        }
    }

    public int getImportance(List<Employee> employees, int id) {
        int sum=0;
        Iterator<Employee> iterator=employees.iterator();
        Employee e=new Employee();
        while (iterator.hasNext()){
            e=iterator.next();
            if(e.id==id){
                sum+=e.importance;
                break;
            }
        }
        List<Integer> list=e.subordinates;
        Iterator<Integer> iterator1=list.iterator();
        while (iterator1.hasNext()){
            int subid=iterator1.next();
            sum+=getImportance(employees,subid);
        }
        return sum;
    }

    /**
     * 868二进制间距
     * @param N
     * @return
     */
    public int binaryGap(int N) {
        int start=0,end=0;
        while (N!=0&&N%2!=1){
            N=N/2;
            start++;
            end++;
        }
        int max=end-start;
        if(N==1) return max;
        while(N!=0){
            end++;
            if(N%2==1){
                int temp=end-start;
                start=end;
                max=max>temp?max:temp;
            }else{
            }
            N=N/2;
        }
        return max;
    }

    /**
     * 665非递减数列
     * @param nums
     * @return
     */
    public boolean checkPossibility(int[] nums) {
        int len=nums.length-1;
        int count=0;
        for(int i=0;i<len;i++){
            if(nums[i]>nums[i+1]){
                count++;
                if(count>=2) return false;
                if(nums[i+1]<nums[i-1]) return false;
            }
        }
        return true;
    }

    /**
     * 429 N叉树的层次遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> node=new ArrayList<>();
        Queue<Node> queue=new LinkedList<>();
        if(root==null){
            return res;
        }
        queue.add(root);
        Node n=null;
        while (queue.size()>0){
            int num=queue.size();
            node=new ArrayList<>();
            for(int i=0;i<num;i++){
                n=queue.poll();
                node.add(n.val);
                List<Node> list=n.children;
                Iterator<Node> iterator=list.iterator();
                while (iterator.hasNext()){
                    queue.add(iterator.next());
                }
            }
            res.add(node);
        }
        return res;
    }

    /**
     * 680验证回文字符串II
     * @param s
     * @return
     */
    public boolean validPalindrome(String s) {
        return validPalin(s,0);
    }

    private boolean validPalin(String s, int n) {
        int len=s.length();
        char cs[]=s.toCharArray();
        int i=0,j=len-1;
        while (i<j){
            if(cs[i]==cs[j]){i++;j--;}
            else {
                n=n+1;
                if(n>=2) return false;
                else {
                    return (validPalin(s.substring(i+1,j+1),n)||validPalin(s.substring(i,j),n));
                }
            }
        }
        return true;
    }

    /**
     * 697数组的度
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer, int[]> map = new HashMap<>();
        int maxFre = 0;
        int minLen = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i]))
            {
                map.get(nums[i])[1] = i;
                map.get(nums[i])[2]++;
            }
            else {
                int[] numInfo = new int[3];
                numInfo[0] = i;
                numInfo[1] = i;
                numInfo[2] = 1;
                map.put(nums[i], numInfo);
            }
            maxFre = Math.max(maxFre, map.get(nums[i])[2]);
        }
        for(int num: map.keySet())
            if(maxFre == map.get(num)[2])
                minLen = Math.min(minLen, map.get(num)[1] - map.get(num)[0] + 1);
        return minLen;

    }

    public String toLowerCase(String str) {
        int len=str.length();
        char []cs=str.toCharArray();
        for(int i=0;i<len;i++){
            char c=cs[i];
            if(c>='A'&&c<='Z'){
                cs[i]=Character.toLowerCase(c);
            }
        }
        return new String(cs);
    }

    /**
     * 872叶子相似的树
     * @param root1
     * @param root2
     * @return
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1=new ArrayList<>();
        addLeaf(root1,list1);
        List<Integer> list2=new ArrayList<>();
        addLeaf(root2,list2);
        Collections.sort(list1);
        Collections.sort(list2);
        if(list1.size()!=list2.size())return false;
        Iterator<Integer> iterator1=list1.iterator();
        Iterator<Integer> iterator2=list2.iterator();
        while (iterator1.hasNext()){
            if(iterator1.next()!=iterator2.next())return false;
        }
        return true;
    }

    private void addLeaf(TreeNode root1, List<Integer> list1) {
        if(root1.left!=null){
            addLeaf(root1.left,list1);
        }
        if(root1.right!=null){
            addLeaf(root1.right,list1);
        }
        if(root1.left==null&&root1.right==null){
            list1.add(root1.val);
        }
    }

    public ListNode middleNode(ListNode head) {
        ListNode p1=head,p2=head;
        while (p2!=null&&p2.next!=null){
            p1=p1.next;
            p2=p2.next;
            p2=p2.next;
        }
        return p1;
    }


    public List<String> readBinaryWatch(int num) {
        List<String> res=new ArrayList<>();
        boolean []visit=new boolean[10];
        readBinaryWatchOne(res,visit,num,0);
        return res;
    }

    private void readBinaryWatchOne(List<String> res, boolean[] visit, int num,int index) {
        if(num==0){
            String s=binary2str(visit);
            if(s.equals("")){
                return;
            }
            res.add(s);
        }else {
            for(int i=index;i<10;i++){
                if(visit[i])continue;
                else {
                    visit[i]=true;
                    readBinaryWatchOne(res,visit,num-1,i);
                    visit[i]=false;
                }
            }
        }
    }

    private String binary2str(boolean[] visit) {
        int begin=0,end=0;
        if(visit[0])begin+=8;
        if(visit[1])begin+=4;
        if(visit[2])begin+=2;
        if(visit[3])begin+=1;
        if(visit[4])end+=32;
        if(visit[5])end+=16;
        if(visit[6])end+=8;
        if(visit[7])end+=4;
        if (visit[8])end+=2;
        if (visit[9])end+=1;
        if(begin>=12||end>=60)return "";
        if(end<10){
            return begin+":0"+end;
        }else {
            return begin+":"+end;
        }
    }

    public String reverseOnlyLetters(String S)
    {
        char[]data=S.toCharArray();
        int len=data.length;
        int i=0,j=len-1;
        while (i<j)
        {
            while (i<len)
            {
                if((data[i]>='a'&&data[i]<='z')||(data[i]>='A'&&data[i]<='Z'))
                {
                    break;
                }
                i++;
            }
            while (j>0)
            {
                if((data[j]>='a'&&data[j]<='z')||(data[j]>='A'&&data[j]<='Z'))
                {
                    break;
                }
                j--;
            }
            if(i<j)
            {
                char c=data[i];
                data[i]=data[j];
                data[j]=c;
                i++;j--;
            }
        }
        return  new String(data);
    }

    
}
